package greedy_algorithm.leetcode.medium;

/**
 * @author bruin_du
 * @description 剪绳子
 * @date 2022/6/9 23:31
 **/
public class Offer14I_CuttingRope {
    public int cuttingRope(int n) {
        //方法一：贪心法
        method1(n);
        //贪心法优化
        method2(n);

        //方法二：动态规划
        return method3(n);
    }

    private int method1(int n) {
        if(n <= 3) {
            return n - 1;
        }
        int sum = 1;
        while(n >= 3){
            sum *= 3;
            n -= 3;
        }
        if(n == 1){
            sum /= 3;
            n += 3;
        }
        while(n != 0) {
            sum *= 2;
            n -= 2;
        }
        return sum;
    }

    private int method2(int n) {
        if(n <= 3) {
            return n - 1;
        }
        int a = n / 3, b = n % 3;
        if(b == 1) return (int)Math.pow(3,a - 1) * 4;
        if(b == 2) return (int)Math.pow(3,a) * 2;
        return (int)Math.pow(3,a);
    }

    private int method3(int n) {
        if(n <= 3){
            return n - 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i],dp[j] * dp[i - j]);
            }
        }
        return dp[n];
    }
}
